ORDERCHR(1)           User Contributed Perl Documentation          ORDERCHR(1)



NNAAMMEE
       orderchr - determine a chromosome order to minimize cross-over of links

SSYYNNOOPPSSIISS
         orderchr -links linkfile.txt { -anchorfile anchors.txt | -anchorrx REGEX } -karyotype karyotype.txt

DDEESSCCRRIIPPTTIIOONN
       By examining the frequencies of chromosome-chromosome relationships
       defined in the link file, this script suggests a new order for chromo-
       somes that results in fewer cross-overs between links. The order of
       anchor chromosomes is adjusted - links to/from other chromosomes are
       not considered and those chromosomes are not re-ordered.. You can
       define anchors using a file or regular expression.

       Simulated annealing is used to optimize the chromosome order (read
       below about parameters). Run the simulation a couple of times to check
       convergence (finding a global minimum is not guaranteed).

       There are four modes in which the script is run and each mode differs
       in the way anchor chromosomes are defined. In order of increasing con-
       venience, these modes are

       MMOODDEE 11 -- aanncchhoorrss ddeeffiinneedd iinn aa ffiillee ((kkaarryyoottyyppee ffiillee iiss nnoott uusseedd))

         > orderchr -links linkfile.txt -anchorfile anchors.txt

       Order of chromosomes provided in the -anchorfile is optimized.

       MMOODDEE 22 -- aanncchhoorrss ddeeffiinneedd bbyy rreegguullaarr eexxpprreessssiioonn ((kkaarryyoottyyppee ffiillee iiss uusseedd))

         > orderchr -links linkfile.txt -anchorrx chr1 -karyotype karyotype.txt

       All chromosomes are read from the karyotype file and the list is fil-
       tered by the -anchorrx regular expression. Those chromosomes that match
       the regular expression are re-ordered.

       In this example, chromosomes matching "chr1" will be re-ordered (e.g.
       chr1, chr10, chr11, etc).

       MMOODDEE 33 -- nnoo eexxpplliicciitt aanncchhoorrss aarree ddeeffiinneedd ((kkaarryyoottyyppee ffiillee iiss nnoott uusseedd))

         > orderchr -links linkfile.txt

       In the absence of an anchor filter, or a karyotype file, all chromo-
       somes referenced in the link file will be re-ordered.

       This mode is helpful if you don't have a formatted karyotype file yet.

       MMOODDEE 44 -- nnoo eexxpplliicciitt aanncchhoorrss aarree ddeeffiinneedd ((kkaarryyoottyyppee ffiillee iiss uusseedd))

         > orderchr -links linkfile.txt -karyotype karyotype.txt

       In the absence of an anchor filter, all chromosomes in the karyotype
       file are re-ordered.

SSIIMMUULLAATTEEDD AANNNNEEAALLIINNGG
       This method is an optimization method that encourages the discovery of
       a global minimum by traversing the space of solutions with a small (and
       decreasing as simulation runs) chance of visiting less desirable solu-
       tions.

       There are three parameters that control the optimization.

       iitteerraattiioonnss

       The number of iterations to perform. At each iteration, the current
       solution is randomly modified and either accepted or rejected.

       mmaaxx__fflliippss

       The optimization run is split into max_flips equal-sized intervals.
       During each iterval (i=1..max_flips), the number of random chromosome
       pair swaps in the solution is given by

         max_flips - i + 1

       For example, if max_flips is 3 and iterations=1000. Then the number of
       random pair swaps is

         iteration 1-333    3
         iteration 334-666  2
         iteration 667-1000 1

       tteemmpp00

       This parameter determines the probability of a transition to a less
       desirable solution. The transition probability is

         p(dE) = temp0*exp( - dE/t )

       where t=1..0 over the length of the simulation and dE is the relative
       change in the desirability of two solutions.

       If temp0=1, then the probability of accepting a solution that is 10%
       worse (e.g. dE=0.1) is

         p(0.1) = exp (-0.1/1)   = 90%    at start of simulation
                = exp (-0.1/0.5) = 82%    half way through simulation
                = exp (-0.1/0.1) = 37%    90% of the way through simulation

       By lowering temp0, you lower the probability of transition to a less
       desirable solution.

       Do not adjust temp0 unless you feel that the simulation is (a) not
       traversing the solution space sufficiently - in which case make temp0
       larger or (b) too many low-quality solutions are accepted - in which
       case make temp0 smaller.

       ooppttiimmiizzee == mmiinniimmiizzee||mmaaxxiimmiizzee

       Most of the time you'll want to adjust the chromosome order in a way to
       minimize the number of crossing links. However, you can set to maximize
       the number of crossing links by setting

         optimize = maximize

HHIISSTTOORRYY
       * 8 July 2008
           Started and versioned.

BBUUGGSS
AAUUTTHHOORR
       Martin Krzywinski

CCOONNTTAACCTT
         Martin Krzywinski
         Genome Sciences Centre
         Vancouver BC Canada
         www.bcgsc.ca
         martink@bcgsc.ca



perl v5.8.7                       2008-07-08                       ORDERCHR(1)
